/*
 * @lc app=leetcode.cn id=300 lang=java
 *
 * [300] 最长递增子序列
 */

// @lc code=start
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;

        // // 解法2：dp
        // if (nums.length == 0)
        //     return 0;
        // int res = 0;
        // int[] dp = new int[nums.length];
        // for (int i = 0; i < nums.length; i++)
        //     dp[i] = 1;

        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = 0; j < i; j++) {
        //         if (nums[i] > nums[j])
        //             dp[i] = Math.max(dp[i], dp[j] + 1);
        //     }
        //     res = Math.max(res, dp[i]);
        // }
        // return res;
    }

    public int lengthOfLIS(int[] nums, int pre, int cur, int[][] memo) {
        if (cur == nums.length)
            return 0;
        if (memo[pre + 1][cur] > 0)
            return memo[pre + 1][cur];

        int a = 0;
        if (pre < 0 || nums[pre] < nums[cur]) {
            a = lengthOfLIS(nums, cur, cur + 1, memo) + 1;
        }
        int b = lengthOfLIS(nums, pre, cur + 1, memo);
        memo[pre + 1][cur] = Math.max(a, b);
        return memo[pre + 1][cur];
    }
}
// @lc code=end
